home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / impl / iv_tree.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  7.8 KB  |  303 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  iv_tree.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_IV_TREE_H
  17. #define LEDA_IV_TREE_H
  18.  
  19. //--------------------------------------------------------------------
  20. //  
  21. //  Interval Trees
  22. //
  23. //  Michael Seel (1990/91)
  24. //
  25. // Implementation as described in
  26. // Kurt Mehlhorn: Data Structures and Algorithms 3, section VIII.5.1.1
  27. //
  28. //--------------------------------------------------------------------
  29.  
  30. // -----------------------------------------------------
  31. // includes
  32. // -----------------------------------------------------
  33.  
  34. #include <LEDA/basic.h>
  35. #include <LEDA/b_stack.h>
  36. #include <LEDA/list.h>
  37. #include <LEDA/dictionary.h>
  38.  
  39.  
  40.  
  41. // -------------------------------------------------------
  42. // declarations and definitions
  43. // -------------------------------------------------------
  44.  
  45. const BSTACKSIZE = 70 ; // according to tree.size and alpha
  46.                  // here: tree.size <= 10^9
  47.                  //       alpha = 0.25 ( worst case )
  48.  
  49. enum children { _left = 0 , _right = 1 };
  50. enum leaf_or_node { leaf = 0 , node = 1 } ;
  51.  
  52. class iv_node;
  53. class iv_tree;
  54.  
  55. typedef int       x_typ;
  56. typedef iv_node*  iv_item;
  57.  
  58.  
  59.  
  60.  
  61. // -----------------------------------------------------------
  62. // zur Unterscheidung bei Eingabe von Intervallen gleicher
  63. // x-Koordinate wird als Split-Value nicht nur die linke
  64. // Intervall-Grenze, sondern auch eine durchlaufende Nummer
  65. // als zweite Komponente abgespeichert, ueber der auch eine
  66. // compare Funktion deklariert wird.
  67. // -----------------------------------------------------------
  68.  
  69.  
  70. struct split_pair
  71.     {
  72.       x_typ key1;
  73.       int   key2;
  74.       split_pair(x_typ x=0,int n=0) { key1=x;key2=n; }
  75.       split_pair(split_pair& s) {key1=s.key1;key2=s.key2;}
  76.       int  cmp(x_typ x1,x_typ x2) {return int(x1)-int(x2);}
  77.       void print() {cout << "(" << key1 << "/" << key2 << ")"; }
  78.     };
  79.  
  80. typedef split_pair* split_item;
  81.  
  82. // -----------------------------------------------------------
  83. // zur Abspeicherung der x- und y-orientierten Knotenlisten !!
  84. // Die Dictionary-Deklaration wird nach erstellen der geeig-
  85. // neten bb_trees durch diese ersetzt. Bis dahin kostet bei
  86. // den rb_trees die Vereinigung zweier geordneter Listen 
  87. // (Laenge beider Listen insgesamt n) die Zeit O(n log n)
  88. // anstatt wie angestrebt O(n) !!!
  89. // -----------------------------------------------------------
  90.  
  91. // -------------------------------------------------------
  92. // interval, interval_item und query-Rueckgabetyp
  93. // -------------------------------------------------------
  94.  
  95. struct interval { x_typ koo1;
  96.           x_typ koo2;
  97.           interval(x_typ x,x_typ y) {koo1=x;koo2=y;}
  98.                   int cmp(x_typ x1,x_typ x2) {return int(x1)-int(x2);}
  99.                   void print() {cout << "[" << koo1 << "/" << koo2 << "]"; }
  100.                 };
  101.  
  102. typedef interval* interval_item;
  103.  
  104.  
  105. typedef list<interval_item> interval_list;
  106.  
  107. // -------------------------------------------------------------
  108. // compare-Funktion zu Dictionary
  109. // -------------------------------------------------------------
  110.  
  111. inline int compare (interval_item& p, interval_item& q)
  112. { int a = p->cmp(p->koo1,q->koo1);
  113.   return (a) ? a : p->cmp(p->koo2,q->koo2);
  114.  }
  115.  
  116.  
  117.  
  118. typedef dictionary<interval_item,int> nodelist;
  119. typedef nodelist* nodelist_p;
  120.  
  121. // -------------------------------------------------------
  122. // class iv_node     
  123. // -------------------------------------------------------
  124.  
  125. class iv_node {
  126.  
  127.   nodelist_p    x_nl;
  128.   nodelist_p    y_nl;
  129.   split_item    split_val;   // nach split_val (= Pointer auf das
  130.                  // Paar (linke Intervallgrenze;-lfnr)
  131.                  // wird geordnet
  132.   int gr;
  133.   iv_item son[2];
  134.  
  135.   friend class iv_tree;
  136.  
  137. public:
  138.  
  139.   nodelist_p    x_nodelist()           { return x_nl; }
  140.   nodelist_p    y_nodelist()           { return y_nl; }
  141.   split_item    split_value()          { return split_val; }
  142.  
  143.   int         blatt()                { return (gr==1); }
  144.   int         groesse()              { return gr; }
  145.  
  146.   float bal()
  147.     { if (blatt()) return 0.5;
  148.       else return float(float(son[_left]->groesse())/float(gr));
  149.         }
  150.  
  151.   iv_node(split_item s_i, leaf_or_node ln=leaf, iv_item ls=0, iv_item rs=0)
  152.   { 
  153.     x_nl = new nodelist;
  154.     y_nl = new nodelist;
  155.     split_val = new split_pair(*s_i);
  156.     son[_left] = ls;
  157.     son[_right] = rs;
  158.     if (ln==leaf)
  159.     gr=1;
  160.     else 
  161.     gr = ls->groesse()+rs->groesse();
  162.    }
  163.  
  164.  
  165.  ~iv_node()
  166.   { delete x_nl;
  167.     delete y_nl;
  168.     delete split_val;
  169.   }
  170.  
  171.   LEDA_MEMORY(iv_node)
  172.  
  173. }; 
  174.  
  175.  
  176. // -------------------------------------------------------
  177. // class iv_tree     
  178. // -------------------------------------------------------
  179.  
  180. class iv_tree {
  181.  
  182.   iv_item root;
  183.   int   anzahl; 
  184.   float alpha;
  185.   float d;
  186.   b_stack<iv_item> st;
  187.   int   interval_nb;         //  jedes Intervall, das eingefuegt wird,
  188.                  //  erhaelt eine laufende Nummer.
  189.                  //  in dieser Implementation wird diese
  190.                  //  mit dem Konstruktor auf 0 gesetzt
  191.                  //  und bei jedem Insert inkrementiert
  192.                  //  bei Dauerbenutzung einer Datenstruktur
  193.                  //  droht damit irgendwann ein Overflow.
  194.  
  195.   friend class iv_node;
  196.  
  197.   int cmp (const split_item& p, const split_item& q)
  198.     {
  199.        int a = p->cmp(p->key1,q->key1);
  200.        return (a) ? a : p->key2 -  q->key2;
  201.     }
  202.  
  203.   
  204.   void    lrot(iv_item , iv_item ); 
  205.   void    rrot(iv_item , iv_item ); 
  206.   void    ldrot(iv_item , iv_item ); 
  207.   void    rdrot(iv_item , iv_item ); 
  208.   void    reorganize_nodelist(iv_item , iv_item);
  209.   iv_item search(split_item);
  210.   iv_item ins(interval_item,interval_item,int);
  211.   iv_item sink(iv_item, interval_item, interval_item, int);
  212.   int     del(split_item);
  213.   void    deltree(iv_item);
  214.  
  215.   // split_in_interval ueberprueft ob die erste Komponente des split_value
  216.   // des Knotens v im Interval i liegt
  217.  
  218.   int   split_in_x_interval(iv_item v, interval_item i)
  219.     { if ((i->cmp(i->koo1 , split_value(v)->key1) <= 0)
  220.       && (i->cmp(split_value(v)->key1 , i->koo2) <= 0))
  221.         return 1;
  222.       else
  223.         return 0;
  224.         }
  225.  
  226.   int   split_in_y_interval(iv_item v, interval_item i)
  227.     { if ((i->cmp(i->koo2 , split_value(v)->key1) <= 0)
  228.       && (i->cmp(split_value(v)->key1 , i->koo1) <= 0))
  229.         return 1;
  230.       else
  231.         return 0;
  232.         }
  233.  
  234.   // nodelist_swap vertauscht die Knotenlisten zweier Knoten
  235.  
  236.   void    nodelist_swap(iv_item p, iv_item q)
  237.       { 
  238.         nodelist_p help = p->x_nl;
  239.         p->x_nl = q->x_nl;
  240.         q->x_nl = help;
  241.         help = p->y_nl;
  242.         p->y_nl = q->y_nl;
  243.         q->y_nl = help;
  244.           }
  245.  
  246.   void    y_search(interval_list& il, iv_item v, split_item ys, x_typ x, x_typ y);
  247.   void    check_nodelist(interval_list& il, iv_item v, x_typ x, x_typ y);
  248.   void    get_all_in_tree(interval_list& il, iv_item v);
  249.   void    take_all_iv(interval_list& il, iv_item v);
  250.   void    check_y_iv(interval_list& il, iv_item v, x_typ x);
  251.   void    check_x_iv(interval_list& il, iv_item v, x_typ y);
  252.  
  253.  
  254.   void pr_iv_tree(iv_item, int);
  255.   void pr_iv_list(iv_item);
  256.  
  257. public:
  258.  
  259.   nodelist_p    x_nodelist(iv_item it)   {return (it) ? it->x_nodelist() : 0;}
  260.   nodelist_p    y_nodelist(iv_item it)   {return (it) ? it->y_nodelist() : 0;}
  261.   split_item    split_value(iv_item it)  {return (it) ? it->split_value() : 0;}
  262.  
  263.  // Operationen auf Intervall-B"aumen:
  264.  
  265.   iv_item         iv_insert(x_typ, x_typ);
  266.   void            iv_delete(x_typ, x_typ);
  267.   interval_list   iv_query(x_typ, x_typ);
  268.  
  269.   // zur Datendarstellung folgende Ausgabe-Funktionen:
  270.  
  271.   void          print_split(iv_item);
  272.   void          text(string s) { cout << s; }
  273.   void          pr_list(interval_list& il);
  274.      
  275.   void pr_iv_tree() { pr_iv_tree(root,0); }
  276.  
  277.  
  278.   iv_tree()   :  st(BSTACKSIZE) 
  279.   { 
  280.     root = 0;
  281.     anzahl = 0;
  282.     alpha=0.28;
  283.     d=1/(2-alpha);
  284.     interval_nb = 0;
  285.   }
  286.  
  287.  
  288.   ~iv_tree()  
  289.   { 
  290.    if (root)
  291.      deltree(root);
  292.    root = 0;
  293.    anzahl = 0;
  294.    alpha = 0;
  295.    d = 0;
  296.    interval_nb = 0;
  297.   }
  298.  
  299. };
  300.  
  301.  
  302. #endif
  303.